#!/usr/bin/env python3

"""
Given a m x n matrix, if an element is 0, set its entire row and column to 0
"""

class Solution:
    def set_zeroes(self, matrix):
        row_zero = set()
        col_zero = set()
        n = len(matrix)
        m = len(matrix[0])
        for row_index in range(n):
            row = matrix[row_index]
            for col_index in range(m):
                val = row[col_index]
                if val == 0:
                    if col_index not in col_zero:
                        for back_row_index in range(row_index - 1, -1, -1):
                            matrix[back_row_index][col_index] = 0
                        col_zero.add(col_index)
                    if row_index not in row_zero:
                        for back_col_index in range(col_index - 1, -1 , -1):
                            row[back_col_index] = 0
                        row_zero.add(row_index)
                elif row_index in row_zero or col_index in col_zero:
                    row[col_index] = 0

                    
if __name__ == '__main__':
    s = Solution()
    input = [[-4,-2147483648,6,-7,0],[-8,6,-8,-6,0],[2147483647,2,-9,-6,-10]]
    s.set_zeroes(input)
    print(f'result: {input}')
    input = [[1, 1, 1],
             [1, 0, 1],
             [1, 1, 1]]
    s.set_zeroes(input)    
